package stackAndQueue;

import java.util.Deque;
import java.util.LinkedList;

class MyDeque {
    Deque<Integer> deque;

    public MyDeque() {
        this.deque = new LinkedList<>();
    }

    void poll(int val) {
        if (!deque.isEmpty() && deque.peek() == val) {
            deque.poll();
        }
    }

    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast())
            deque.removeLast();

        deque.add(val);
    }

    int peek() {
        return deque.peek();
    }
}

public class N239_SlidingWindowMaximum {
    // TODO 只理解自己没写出来。。。。
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) return nums;
        int len = nums.length - k + 1;
        int[] res = new int[len];
        MyDeque deque = new MyDeque();

        int num = 0;

        for (int i = 0; i < k; i++) {
            deque.add(nums[i]);
        }

        res[num++] = deque.peek();

        for (int i = k; i < nums.length; i++) {
            deque.poll(nums[i - k]);
            deque.add(nums[i]);

            res[num++] = deque.peek();
        }
        return res;
    }

    public static void main(String[] args) {
        N239_SlidingWindowMaximum solution = new N239_SlidingWindowMaximum();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] ints = solution.maxSlidingWindow(nums, 3);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }
}
